COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002			SYLLABUS FOR PH.D. QUALIFYING EXAMINATION
C00006 00003					REFERENCES
C00010 00004				RECOMMENDED COURSES:
C00011 ENDMK
C⊗;
		SYLLABUS FOR PH.D. QUALIFYING EXAMINATION
	     IN THE MATHEMATICAL ASPECTS OF COMPUTER SCIENCE


				January 1970


	The outline and reference list provided here are intended to suggest 
and not to delimit the material covered by the exam.

1.	Mathematical Logic ([1] or [2], see the bibliography in [3.1]

	1.1  The Propositional Calculus
	1.2  The Predicate Calculus
  	1.3  Theorem Proving by Computers

2.	Theory of Computability ([4] or [5])

	2.1  Church's Thesis and the equivalence of several definitions of
	     computability, such as Turing computable, Mrkov computable and
	     general recursive.

	2.2  Primitive recursive and partial recursive functions.
	     Ackermann's function.

	2.3  Recursive and recursively enumerable sets.

	2.4  Semi-Thue and Thue systems.  Post productions and normal systems.

3.	Automata Theory p[6]-[9])

	3.1  Finite Automata (deteministic and non-deterministic), regular
	     expressions (Kleene Theorem), right-linear languages and finite
	     semi-groups.
	3.2  Push-down automata (deterministic and non-deterministic) and
	     Context-free languages.

4.	Mathematical Theory of Computation
	
	4.1  Methods for proving properties of:  Compilers, program schemas,
	     and programs.  ([10]-[17])
	4.2  Semantics of Programming Languages. ([18]-[19])

5.	Decision Problems ([9],[12])

	5.1  The Halting problem of Turing machines (and the equivalent
	     problem for recursive functions).
	     The undecidability of:
	     (a)  The word problem for Thue and Semi-thue sstems.
	     (b)  Post's Correspondence problem, and
	     (c)  The First Order Predicate Calculus.
	5.2  Decision problems in connection with subjects described in 
	     Sections 1-4, such as:  decidable cases of the First Order
	     Predicate Calculus, the equivalence problem of program schemas,
	     context-free languages and finite automata.

6. 	Mathematical Background

	6.1  Algebra
	6.2  Set Theory
	6.3  Graph Theory
				REFERENCES

[1]  Mendelson, E., INTRODUCTION TO MATHEMATICAL LOGIC.  Van Nostrand (1964).

[2]  Robbin J. W., MATHEMATICAL LOGIC:  A FIRST COURSE. W. A. Benjamin (1969).

[3]  Robinson, J. A. "A Review of Automatic Theorem-Proving". in MATHEMATICAL
    	ASPECTS OF COMPUTER SCIENCE.  American Mathematical Society (1967).

[4]  Davis, M., COMPUTABILITY AND UNSOLVABILITY.  McGraw-Hill (1958).

[5]  Hermes, H., ENUMERABILITY, DECIDABILITY AND COMPUTABILITY.  Academic Press (1965).

[6]  Nelson, R. J., INTRODUCTION TO AUTOMATA. John Wiley and Sons (1968).

[7]  Minsky, M., COMPUTATION:  FINITE AND INFINITE MACHINES.  Prentice-Hall (1967).

[8]  Rabin, M. O. and Scott, D., "Finite Automata and Their Decision Problems".
	IBM JOURNAL 3, 114 (1959).  Also in SEQUENTIAL MACHINES (ed. E. F. Moore),
	Addison-Wesley (1969).

[9]  Hopcroft, J. and Ullman J., FORMAL LANGUAGES AND THEIR RELATION TO AUTOMATA.
	Addison-Wesley (1969).

[10] McCarthy, J., and Painter, J., "Correctness of a Compiler for Arithmetic
	Expressions". in PROCEEDINGS OF SYMPOSIA IN APPLIED MATHEMATICS, Vol. 19
	(1967).

[11] Rutledge, J. D., "On Ianov Program Schemata." JOURNAL OF THE ACM, Vol. 11, 
	No. 1 (1964), pp. 1-9.

[12] Luckham, D. C., Park, D. M. R. and Paterson, M. S., ON FORMALISED COMPUTER
	PROGRAMS.  (Preliminary draft) Programming Research Group, Oxford University
	(August 1967).
[13] Floyd, R. W., "Assigning Meaning to Programs". in MATHEMATICAL ASPECTS OF
	COMPUTER SCIENCE.  American Mathematical Society (1967).

[14] McCarthy, J., "Towards a Mathematical Science of Computation." in PROCEEDINGS
	IFIP CONGRESS 62, North-Holland, Amsterdam (1962), pp. 21-26.

[15] McCarthy, J., "Basis for a Mathematical Theory of Computation." in COMPUTER
	PROGRAMMING AND FORMAL SYSTEMS (Braffort and Hirschberg, eds.), North-
	Holland (1963), pp. 33-70

[16] Manna, Z., "Properties of Programs and the First-Order Predicate Calculus."
	in JACM, Vol. 16, No.2 (April 1969).

[17] Manna, Z. and Pnueli, A., "Formalization of Properties of Functional Programs".
	in ACM SYMPOSIUM ON THEORY OF COMPUTING (May 1969).

[18] McCarthy, J., "A Formal Description of a Subset of Algol". in FORMAL LANGUAGE
	DESCRIPTION LANGUAGES FOR COMPUTER PROGRAMMING.  (Steele, ed.). North-
	Holland (1966).

[19] Lucas, P., Lauer, P., Stigleitner, H., METHOD AND NOTATION FOR THE FORMAL
	DEFINITION OF PROGRAMMING LANGUAGES.  IBM Lab, Vienna, TR 25.087 (June 1968).
			RECOMMENDED COURSES:

	Phil. 160 AB, 162
	CS 208 (CS 156); CS 243 (CS 256 AB)
	Theory of Computation Seminar

			RELATED COURSES:

	EE 384, 484
	Math 292 ABC, 293 ABC